package 并查集理论基础;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/6/5 22:10
 * @description:
 */
public class union_find_set {

    private static int[] father;
    private static int[] rank;

    public void make_set(int n) {
        father = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    public int find(int u) {
        if (u != father[u]) {
            // 路径压缩
            father[u] = find(father[u]);
        }
        // 返回当前节点 u 的父节点
        return father[u];
    }

    public void union(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        // 通过树高优化 union，树低的连接到树高的集合中
        if (rank[u] < rank[v]) {
            father[u] = v;
        } else if (rank[u] > rank[v]) {
            father[v] = u;
        } else {
            father[v] = u;
            rank[u] += 1;
        }
    }

    public static void main(String[] args) {
        union_find_set unionSet = new union_find_set();
        unionSet.make_set(10);
        System.out.println(Arrays.toString(father));
        unionSet.union(0, 1);
        unionSet.union(1, 2);
        unionSet.union(2, 3);
        unionSet.union(3, 4);
        unionSet.union(4, 5);
        unionSet.union(5, 6);
        unionSet.union(6, 7);
        unionSet.union(7, 8);
        unionSet.union(8, 9);

        System.out.println(Arrays.toString(father));
    }

}
